本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

今天算是進入我們倒數第二個主題了，雖然不知道前面的內容大家能不能吸收，或是了解了多少，但是.....The show must go on!!!!!?

今天開始一連三天，我們要介紹的是Dynamic Programming這個類別的演算法，這種演算法有啥特別的勒？讓我們看下去吧～

Dynamic Programming的概念

Dynamic Programming是一個使用小問題解決方式來解決大問題的演算法，主要的想法大概如下：

1. 把一個大問題拆成數個相關的小問題
2. 解決這些小問題
3. 將小問題的解答記錄下來
4. 重新組合這些小問題的解答，藉此來得到大問題的解答。

這樣看起來，是不是跟Divide and Conquer有點像（忘記的人點這邊)，但兩者之間的差異在於經過Divide and Conquer所取得的小問題解答之間是獨立的，也就是用完即丟，一種拋棄式的概念，如果回想Merge Sort的Pseudo-code，雖然他將Array拆成很多個片段，然後在進行組合，可是，這個片段與組合的過程中，變數本身的能見度僅局限於該方法，也就是說，當這個方法結束之後，這個變數就被資源回收了；然而，Dynamic Programming會把所有小問題解答給記錄下來，然後再利用這些小解答進行重複使用的組合或判斷，進而取得最後大問題的解答，因此每一個小解答間是相依的；這就是兩者之間最大的差別。也因為Dynamic Programming會記錄所有小解答，使其屬於利用空間換取時間的一種演算法。

範例：Coin-Row Problem

問題：如果有一串硬幣上面分別有不同的金額(8, 3, 4, 12, 7, 5)，請從中選出最大金額的硬幣組合且這些硬幣不能相連？

在解決一個問題之前，我們要先了解這個問題的條件，按照這個問題來說，現在有六個硬幣，編號(n)分別是0, 1, 2, 3, 4, 5, 6，假如我選了編號0的硬幣，我就不能選編號1的硬幣，在這樣的規則下，我必須要找出擁有最大金額的金幣組合，若將這個金幣按照編號排列，並依序將面額相加，基本上會有兩種情況：

1. 我選了當前硬幣 ➜ 目前合計金額為自己＋前兩格金幣的面額 ➜ Ｃn + F(n-2)
2. 我不選當前硬幣 ➜ 合計金額為上一次的合計金額 ➜ F(n-1)

而我們就要上面這兩種可能性選出最大值記錄下來，便可取得一個計算過後的Table，如下GIF：

然後，我們要利用這個Table進行Backtracking，從中找出最大的組合，其方式為倒序的方式將合計的金額兩兩比較並取大值，便表示該硬幣被選擇，直到回到第一個硬幣，如下GIF：

因為問題要求所選擇的硬幣不能相連，故在比較時，會跳過幾個值再去進行比較；另外過程中發現有兩個值會有同樣的結果，因此這個範例會產生兩種最終結果。

結果：兩個組合 ➜ (C4, C6), (C1, C3, C6)

小結

Dynamic Programming也是將大問題拆解成小問題處理，但是過程中會紀錄下所有小問題的解答，再依據這些小問題的解答重新讀取使用、計算、組合，進而得出最終的結果。

預告

明天我們將會介紹另一種Dynamic Programming的演算法 - Edit Distance。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin